Search results for "MR 68Q70"

showing 1 items of 1 documents

Varieties Generated by Certain Models of Reversible Finite Automata

2006

Reversible finite automata with halting states (RFA) were first considered by Ambainis and Freivalds to facilitate the research of Kondacs-Watrous quantum finite automata. In this paper we consider some of the algebraic properties of RFA, namely the varieties these automata generate. Consequently, we obtain a characterization of the boolean closure of the classes of languages recognized by these models.

finite monoidNested word[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]Quantum automaton0102 computer and information sciences[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Computer Science::Computational Complexityω-automatonregular language01 natural sciences[MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR]Regular languageQuantum finite automata0101 mathematicsReversible automatonMathematicsDiscrete mathematicsFinite-state machine010102 general mathematicsNonlinear Sciences::Cellular Automata and Lattice GasesMR 68Q70AutomatonClosure (mathematics)010201 computation theory & mathematicsAutomata theoryComputer Science::Formal Languages and Automata Theory
researchProduct